Optimización Convexa: Más allá de la convexidad básica: Preservación mediante el supremo puntual

Aunque la convexidad básica cubre sumas y escalado, la preservación de la convexidad a través del supremo puntual es una operación fundamental para construir funciones convexas no triviales y establecer dualidad. Establece que, incluso si tenemos una familia infinita no contable de funciones convexas, su "envolvente superior" sigue siendo convexa. Este puente nos permite analizar formas convexas complejas utilizando componentes lineales simples.

1. La Definición Técnica

Para una familia de funciones $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, el supremo puntual se define como:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

El dominio de esta función es el conjunto de puntos donde todas las funciones de la familia están definidas y el supremo es finito:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ para todo } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

La Perspectiva del Epigrafo

Geométricamente, el epígrafo de la función supremo es la intersección de los epígrafos individuales:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Dado que cada epígrafo individual es un conjunto convexo (debido a la convexidad de $f(x, y)$ en $x$), y la intersección de cualquier número de conjuntos convexos también es convexa, la convexidad de $g(x)$ está garantizada.

2. Ejemplos Importantes

Función de soporte: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Esta función siempre es convexa, independientemente de si el conjunto $C$ es convexo o no, porque es el supremo de funciones lineales (afines) de $y$.
Distancia al punto más alejado: $f(x) = \sup_{y \in C} \|x - y\|$. Incluso para un conjunto $C$ de forma irregular, $f(x)$ es convexa en $x$ porque la norma es una función convexa de $x$.
Valor propio máximo: Para una matriz simétrica $X$, $f(X) = \lambda_{\max}(X)$ es convexa. Esto se deriva del cociente de Rayleigh: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. Es el supremo de funciones lineales de $X$.

Teorema: Representación mediante funciones afines

Teorema

Casi toda función convexa puede expresarse como el supremo puntual de una familia de funciones afines (subestimadores globales).

Intuición

En cada punto $x_0$, una función convexa $f$ tiene un hiperplano de soporte (una función afín $h(x) = f(x_0) + g^T(x-x_0)$). Al tomar el supremo de todos estos hiperplanos de soporte, reconstruimos exactamente la función $f$.

🎯 Principio Fundamental

El supremo puntual preserva la convexidad y el ínfimo puntual preserva la concavidad. Este es el secreto detrás de la convexidad de las normas, funciones espectrales y problemas duales.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ es convexa si } f(\cdot, y) \text{ es convexa } \forall y$$

PREGUNTA 1

Si $f_1(x), f_2(x), \dots, f_n(x)$ son funciones convexas, ¿qué podemos decir sobre $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ es siempre convexa.

$g(x)$ es convexa solo si todas las $f_i$ son lineales.

$g(x)$ es cóncava.

$g(x)$ es solo cuasiconvexa.

PREGUNTA 2

La función de soporte $S_C(y) = \sup_{x \in C} y^T x$ es convexa en $y$ incluso si $C$ es un conjunto no convexo. ¿Por qué?

Porque $y^T x$ es lineal (y por tanto convexa) en $y$ para cualquier $x$ fijo.

Porque el conjunto $C$ se trata automáticamente como su envolvente convexa.

Porque el producto interno siempre es una función positiva.

Las funciones de soporte solo son convexas si $C$ es acotado.

PREGUNTA 3

¿Cuál es la relación entre el epígrafo de $g(x) = \sup f_i(x)$ y los epígrafos individuales $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

No hay relación directa.

PREGUNTA 4

La norma espectral de una matriz $\|X\|_2 = \sigma_{\max}(X)$ es convexa porque...

Es el supremo de las funciones convexas $\|Xv\|_2$ sobre los vectores unitarios $v$.

La suma de los valores singulares siempre es convexa.

Todas las normas son funciones lineales.

Las funciones matriciales siempre son convexas en el cono semidefinido positivo.

PREGUNTA 5

Si tomamos el ínfimo puntual de una familia de funciones cóncavas, ¿cuál es el resultado?

Una función cóncava.

Una función convexa.

Una función lineal.

Depende del dominio.

Desafío: Dualidad y Funciones Conjugadas

MATH008 Análisis Avanzado

En análisis convexo, la función conjugada $f^*$ se define mediante el supremo puntual de funciones afines: $f^*(y) = \sup_x (y^T x - f(x))$. Esta transformación es vital para problemas de optimización dual.

[Respuesta breve] Condición de segundo orden para convexidad. Prueba que una función dos veces diferenciable $f$ es convexa si y solo si su dominio es convexo y $\nabla^2 f(x) \succeq 0$ para todo $x \in \mathbf{dom} f.

Solución: Al restringir $f$ a una línea arbitraria $g(t) = f(x + tv)$, la convexidad de $f$ es equivalente a $g''(t) \geq 0$ para todo $v$ y todo $t$ tal que $x+tv \in \text{dom } f$. Dado que $g'(t) = \nabla f(x + tv)^T v$ y $g''(t) = v^T \nabla^2 f(x + tv) v$, la condición $g''(t) \geq 0$ para todo $v$ es equivalente a que la matriz Hessiana sea semidefinida positiva: $\nabla^2 f(x) \succeq 0$.

[Respuesta breve] Gradiente y Hessiano de la función conjugada. Supón que $\bar{y}$ y $\bar{x}$ están relacionados por $\bar{y} = \nabla f(\bar{x})$, y que $\nabla^2 f(\bar{x}) \succ 0$. (a) Muestra que $\nabla f^*(\bar{y}) = \bar{x}$. (b) Muestra que $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}. (Salida requerida: 250 palabras)

Respuesta de referencia del instructor: Para abordar la parte (a), recordemos la definición de la función conjugada $f^*(y) = \sup_x (y^T x - f(x))$. Para un valor fijo $y = \bar{y}$, si $f$ es diferenciable y convexa, el supremo se alcanza en el punto donde el gradiente de la función objetivo $h(x) = \bar{y}^T x - f(x)$ se anula. Al establecer $\nabla_x (\bar{y}^T x - f(x)) = 0$ obtenemos $\bar{y} = \nabla f(x)$. Dado que el problema establece $\bar{y} = \nabla f(\bar{x})$, se deduce que $\bar{x}$ es el maximizador. Por la propiedad de la función conjugada en el punto de optimalidad, tenemos $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Al derivar ambos lados respecto a $\bar{y}$ y aplicar el teorema del envolvente (o el hecho de que $\bar{x}$ es el optimizador), obtenemos $\nabla f^*(\bar{y}) = \bar{x}$. Esto confirma que el gradiente de la función conjugada actúa como la aplicación inversa del gradiente de la función original.

For part (b), we differentiate the relationship $\nabla f^*(\nabla f(x)) = x$ with respect to $x$ using the chain rule. This gives $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, where $I$ is the identity matrix. Substituting $\bar{y} = \nabla f(\bar{x})$, we get $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Since we are given $\nabla^2 f(\bar{x}) \succ 0$, the Hessian is invertible. Thus, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}$. This elegant result shows that the local curvature of the conjugate function is the reciprocal (or inverse matrix) of the curvature of the original function at corresponding points. This relationship is central to the analysis of Newton-type methods in dual space and the understanding of Legendre transforms in physics and optimization.